package tsp;

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created by alex on 22/12/2016.
 */
public class TSPSolver {
    String filePath = "src/testtsp/TSP0.txt";
    int MAXGENERATION = 40000;

    static int cc = 0;

    int cityNum;

    // 种群规模
    int scale;

    double[][] distance;
    double[][] location;
    int[] bestTour;
    int bestIndex;
    double leastDis = Double.MAX_VALUE;
    double avedistance;

    int[][] population;
    int[][] winners;

    double Pc = 0.5;
    double Pm = 0.2;

    double basePc = 0.5;
    double basePm = 0.05;

    double maxPc = 0.9;
    double maxPm = 0.8;

    double[] P;
    double[] fitness;

    List<Double> leastDistances = new ArrayList<>();
    List<Double> aveDistances = new ArrayList<>();

//    double[] winnerFitness;
//    double aveFitness;
//    double bestFitness;


    double alpha;
    double beta;

    public TSPSolver(int scale) {
        this.scale = scale;
        if (scale % 2 == 1) {
            this.scale += 1;
        }
        P = new double[scale];
        fitness = new double[scale];
//        winnerFitness = new double[scale];
        init();
    }

    private void init() {
        File file = new File(filePath);
        try {
            BufferedReader br = new BufferedReader(new FileReader(file));
            String line = br.readLine();
            cityNum = Integer.parseInt(line);
            location = new double[cityNum][2];
            int count = 0;
            String[] ss;
            while ((line = br.readLine()) != null) {
                ss = line.split(" ");
                location[count][0] = Integer.parseInt(ss[1]);
                location[count][1] = Integer.parseInt(ss[2]);
                count++;
            }

            initDistance();
            population = new int[scale][cityNum];
            winners = new int[scale][cityNum];
            bestTour = new int[cityNum];

            initPopulation();
            initPara();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void initPara() {
        int n = MAXGENERATION / 3;
        alpha = (maxPc - this.Pc) / (double) n;
        beta = (maxPm-this.Pm) / (double) n;
    }


    private void initDistance() {
        distance = new double[cityNum][cityNum];
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                if (i > j) {
                    distance[i][j] = distance[j][i];
                } else if (i == j) {
                    distance[i][j] = 0;
                } else {
                    distance[i][j] = Math.sqrt(Math.pow(location[i][0] - location[j][0], 2)
                            + Math.pow(location[i][1] - location[j][1], 2));
                }
            }
        }
    }


    private void initPopulation() {
        Random random = new Random(System.currentTimeMillis());
        int i, j, k;
        for (k = 0; k < scale; k++) {
            population[k][0] = random.nextInt(65535) % cityNum;
            for (i = 1; i < cityNum; ) {
                population[k][i] = random.nextInt(65535) % cityNum;
                for (j = 0; j < i; j++) {
                    if (population[k][i] == population[k][j]) {
                        break;
                    }
                }
                if (j == i) {
                    i++;
                }
            }
        }
    }

    private void evaluate() {
        double dis = 0;
        double mindis = Double.MAX_VALUE;
        int x, y;
        int index = 0;
        double ave = 0;
        for (int i = 0; i < scale; i++) {
            dis = 0;
            for (int j = 0; j < cityNum - 1; j++) {
                x = population[i][j];
                y = population[i][j + 1];
                dis += distance[x][y];
            }
            x = population[i][cityNum - 1];
            dis += distance[x][population[i][0]];
            if (dis < mindis) {
                mindis = dis;
                index = i;
            }
            ave+=dis;
        }
        ave/=scale;
        if (mindis < leastDis) {
            leastDis = mindis;
            System.out.println("leastDis is "+leastDis);
            copy(population[index], bestTour);
            print(bestTour);
            bestIndex = index;
        }

        aveDistances.add(ave);
        leastDistances.add(leastDis);

        if (cc % 100 == 0) {
            System.out.println("CC is " + cc);
            System.out.println("Pc is " + Pc);
            System.out.println("Pm is " + Pm);
            System.out.println("least distance is " + leastDis);
//            System.out.println("best fitness is " + bestFitness);
//            System.out.println("ave fitness is " + aveFitness);
        }
        cc++;

    }

    private void computeFitness() {
        for (int i = 0; i < scale; i++) {
            fitness[i] = computeFitness(population[i]);
        }
    }

    //直接以距离作为适应度
    private double computeFitness(int[] tour) {
        double dis = 0;
        int x, y = 0;
        for (int i = 0; i < cityNum - 1; i++) {
            x = tour[i];
            y = tour[i + 1];
            dis += distance[x][y];
        }
        dis += distance[y][tour[0]];
        if(leastDis!=Double.MAX_VALUE)
            return 1000.0 / dis;
        else
            return 1000.0/dis-leastDis+1;
    }

    private void computeP() {
        double sumFitness = 0;
        double aveFitness = 0;
        for (int i = 0; i < scale; i++) {
            sumFitness += fitness[i];
        }

        aveFitness = sumFitness / scale;
        sumFitness = 0;
        for (int i = 0; i < scale; i++) {
            if (fitness[i] < (aveFitness / 2)) {
                fitness[i] = 0;
            } else {
                fitness[i] -= aveFitness / 2;
            }
            sumFitness += fitness[i];
        }

        P[0] = fitness[0]/sumFitness;
        for (int i = 1; i < scale; i++) {
            P[i] = fitness[i] / sumFitness+P[i-1];
        }
//        System.out.println(P[scale-1]);
    }


    public void select() {
        copy(bestTour, winners[0]);
//        bestFitness = fitness[bestIndex];
//        aveFitness = bestFitness;
        for (int i = 1; i < scale; i++) {
            double random = Math.random();
            int index = 0;

            for (int j = 0; j < P.length; j++) {
                if (random < P[j]) {
                    index = j;
                    break;
                }
            }
            copy(population[index], winners[i]);
//            aveFitness += fitness[index];
//            winnerFitness[i] = fitness[index];
        }
//        aveFitness /= scale;
    }

    private void cross() {
        for (int i = 0; i < scale - 1; i += 2) {
            double r = Math.random();
            if (r < Pc) {
                int low = (int) (Math.random() * cityNum);
                int high = (int) (Math.random() * cityNum);
                while (low == high) {
                    high = (int) (Math.random() * cityNum);
                }
                if (low > high) {
                    int j = low;
                    low = high;
                    high = j;

                }

                int[] gene1 = new int[cityNum];
                int[] gene2 = new int[cityNum];

                int[] tmp1 = new int[cityNum];
                int[] tmp2 = new int[cityNum];

                int[] mid1 = new int[high - low + 1];
                int[] mid2 = new int[high - low + 1];

                for (int j = 0; j < mid1.length; j++) {
                    mid1[j] = winners[i][low + j];
                    mid2[j] = winners[i + 1][low + j];
                }

                for (int j = 0; j < cityNum - high - 1; j++) {
                    tmp1[j] = winners[i][j + high + 1];
                    tmp2[j] = winners[i + 1][j + high + 1];
                }
                for (int j = 0; j < low; j++) {
                    tmp1[j + cityNum - high - 1] = winners[i][j];
                    tmp2[j + cityNum - high - 1] = winners[i + 1][j];
                }
                for (int j = 0; j < high - low + 1; j++) {
                    tmp1[j + cityNum - high - 1 + low] = winners[i][j + low];
                    tmp2[j + cityNum - high - 1 + low] = winners[i + 1][j + low];
                }

                int count1 = 0;
                int count2 = 0;

                //找到low个不在中间基因里的
                for (int j = 0; j < low; ) {
                    if (!inside(tmp1[count1], mid2)) {
                        gene1[j] = tmp1[count1];
                        j++;
                    }
                    count1++;
                }

                for (int j = 0; j < low; ) {
                    if (!inside(tmp2[count2], mid1)) {
                        gene2[j] = tmp2[count2];
                        j++;
                    }
                    count2++;
                }

                for (int j = low; j <= high; j++) {
                    gene1[j] = mid2[j - low];
                    gene2[j] = mid1[j - low];
                }

                for (int j = high + 1; j < cityNum; ) {
                    for (int k = 0; k < cityNum; k++) {
                        if (!inside(tmp1[k], gene1, j)) {
                            gene1[j] = tmp1[k];
                            j++;
                        }
                    }
                }


                for (int j = high + 1; j < cityNum; ) {
                    for (int k = 0; k < cityNum; k++) {
                        if (!inside(tmp2[k], gene2, j)) {
                            gene2[j] = tmp2[k];
                            j++;
                        }
                    }
                }

                copy(gene1, population[i]);
                copy(gene2, population[i + 1]);
            } else {
                copy(winners[i], population[i]);
                copy(winners[i + 1], population[i + 1]);
            }

        }
    }

    private void updatePc(double fit1, double fit2) {
        double big = fit1;
        if (fit2 > fit1) {
            big = fit2;
        }

    }

    private void updatePm(double fit1) {
    }


    private void showDistance() {
        for (int i = 0; i < distance.length; i++) {
            for (int j = 0; j < distance.length; j++) {
                System.out.print(distance[i][j] + "\t");
            }
            System.out.println();
        }

    }

    private boolean inside(int n, int[] gene) {
        for (int i = 0; i < gene.length; i++) {
            if (n == gene[i]) {
                return true;
            }
        }
        return false;
    }

    private boolean inside(int n, int[] gene, int end) {
        if (gene.length < end) {
            end = gene.length;
        }
        for (int i = 0; i < end; i++) {
            if (n == gene[i]) {
                return true;
            }
        }
        return false;
    }

    private void mutate() {
        for (int i = 1; i < scale; i++) {
            double r = Math.random();
            if (r < Pm) {
                int low = (int) (Math.random() * cityNum);
                int high = (int) (Math.random() * cityNum);
                while (low == high) {
                    high = (int) (Math.random() * cityNum);
                }
                if (low > high) {
                    int j = low;
                    low = high;
                    high = j;
                }
                int[] tmp = new int[cityNum];
                copy(population[i], tmp);
                for (int j = low; j <= high; j++) {
                    population[i][j] = tmp[high - j + low];
                }
            }
        }
    }

    public void evolve() {
        for (int i = 0; i < MAXGENERATION; i++) {

            if (i > MAXGENERATION / 2) {

                Pc = Pc + alpha;
                Pm = Pm + beta;

                Pc = (Pc<0.4)?0.4:Pc;
                Pc = (Pc>1)?1:Pc;
                Pm = (Pm<0.2)?0.2:Pm;
                Pm = (Pm>0.8)?0.8:Pm;
            }

            computeFitness();

            computeP();

            //找到当前最短路径
            evaluate();

            select();

            cross();

            mutate();
        }

        for (int i = 0; i < bestTour.length; i++) {
            System.out.println(bestTour[i]);
        }
        writeFile();
        showDistance();
        writeData();
    }

    private void writeFile() {
        String outfile = "src/testtsp/TSP-";
        int dot = filePath.indexOf(".");
        outfile += filePath.charAt(dot - 1) + "[14302010041].txt";
        try {
            FileWriter fw = new FileWriter(outfile);
            fw.write(leastDis + "\n");
            for (int i = 0; i < bestTour.length; i++) {
                System.out.println(bestTour[i] + 1);
                fw.write((bestTour[i] + 1) + "\n");
            }
            fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void copy(int[] src, int[] dest) {
        for (int i = 0; i < src.length; i++) {
            dest[i] = src[i];
        }
    }

    public void calculateDistance(){
        String fileName ="src/testtsp/answer.txt";
        try {
            int[] location = new int[51];
            BufferedReader br = new BufferedReader(new FileReader(fileName));
            String line;
            int count = 0;
            double dis = 0;
            while ((line = br.readLine())!=null){
                location[count++] = Integer.parseInt(line);
            }
            cityNum = 51;
            for(int i =0;i<cityNum-1;i++){
                dis+=distance[location[i]-1][location[i+1]-1];
            }
            dis+=distance[location[cityNum-1]-1][location[0]-1];
            System.out.println("dis is "+dis);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    private void calculateDistance2(){
        int[] loca = new int[]{2,27,30,25,7,47,22,6,42,23,5,26,0,21,1,15,49,8,48,4,37,10,31,45,50,46,11,36,16,3,17,13,24,12,40,39,18,41,43,14,44,32,38,9,29,33,20,28,19,34,35};
        double dis = 0;
        for (int i =0;i<loca.length-1;i++){
            dis+=distance[loca[i]][loca[i+1]];
        }
        dis+=distance[loca.length-1][0];
        System.out.println("Distance is "+dis);
    }

    private void writeData(){
        try {

            String avefile = "src/testtsp/ave1.txt";
        FileWriter fw = null;
            fw = new FileWriter(avefile);

        for (double ave:aveDistances){
            fw.write(ave+"\n");
        }
        fw.close();

        String bestfile = "src/testtsp/best1.txt";
        FileWriter fw2 = new FileWriter(bestfile);

        for (double best:leastDistances){
            fw2.write(best+"\n");
        }
        fw2.close();
        } catch (IOException e) {
            e.printStackTrace();
        }

    }


    private void print(int[] array) {
        for (int i = 0; i < array.length; i++)
            System.out.print(array[i]+",");
        System.out.println();
    }

    public static void main(String[] args) {
        new TSPSolver(2000).evolve();
    }
}
